package com.zxy.leetcode._00000_00099._00020_00029;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/generate-parentheses/
 *
 * 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，
 * 用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 思路：回溯算法
 */
public class Test00022 {

    public static void main(String[] args) {
        Test00022 test = new Test00022();
        System.out.println(test.generateParenthesis(2));
        System.out.println("============");
        System.out.println(test.generateParenthesis(3));
    }

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        backtrack(list, "", n);
        return list;
    }

    private void backtrack(List<String> result, String selectStr, int n) {
        if (selectStr.length() == 2 * n) {
            result.add(selectStr);
            return;
        }

        if (checkStr(selectStr + "(", n)) {
            backtrack(result, selectStr + "(", n);
        }
        if (checkStr(selectStr + ")", n)) {
            backtrack(result, selectStr + ")", n);
        }
    }

    private boolean checkStr(String str, int n) {
        int c = 0;
        int l = 0;
        int r = 0;
        for (int i=0; i<str.length(); i++) {
            if (str.charAt(i) == '(') {
                c ++;
                l ++;
            }else {
                if (c < 0) {
                    return false;
                }
                c --;
                r ++;
            }
        }
        return l <= n && r <= n && c>=0;
    }

}
